package com.company.linkedList;

import java.util.HashMap;

public class RandomListCopy {
    public static  class Node {
        int val;
        Node next;
        Node random;
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }




    public Node copyRandomList(Node head) {
        return byHashMap(head);
    }



    private Node byHashMap(Node head){
        HashMap<Node,Node> copySet=new HashMap<>();

        //copy all nodes
        Node node = head;
        while (node!=null){
            copySet.put(node,new Node(node.val));
            node = node.next;
        }

        //复制每个节点的关系
        node = head;
        Node copyHead = copySet.get(head);
        while (node!=null){
            Node copy = copySet.get(node);
            copy.next = copySet.get(node.next);
            copy.random = copySet.get(node.random);

            node = node.next;
        }

        return copyHead;

    }



}
